vicefandomcom_it-20200213-history
Valutazione parziale
In Informatica, la valutazione parziale è una tecnica che permette di ottimizzare un programma specializzandolo, in pratica consiste nel fatto di valutare un programma per cui sia nota una parte degli input, in modo tale da ottenere un programma specializzato rispetto a tale input, ma che risulti essere più efficiente dell'originale. Supponiamo di avere un programma P'' ed ''n-upla di valori v1,..,vn (per i suoi primi n'' valori di ingresso), l'obbiettivo è individuare un programma ''P' tale che abbia lo stesso comportamento di P'', quando i suoi primi n ingressi sono v1,..,vn, ma che sia più efficiente. Grazie al Teorema S_{n}^{m} di Kleene sappiamo che un tale sistema può essere realizzato. Esempio f(x,y) = if (x>0 and x<=10) then print(x) else h(y) Se volessimo specializzare ''f per il valore x=5, allora: f5(y) = print(5) Notiamo subito l'ottimizzazione di questa riga di codice, per cui f5 risulta più efficiente per qualunque valore di y''. peval Inoltre, la valutazione parziale, permette di generare automaticamente un compilatore a partire da un interprete Nel contesto dei programmi, il calcolo di una tale funzione di ottimizzazione viene fatto da un '''valutatore parziale peval'; questi è capace di specializzare i programmi scritti in un certo linguaggio M e può essere definito come una funzione: peval: ProgM * dati -> ProgM che, dato un programma scritto nel linguaggio M ed un input dati, per alcuni suoi dati di ingresso, produce un altro programma sempre scritto nel linguaggio M, ma che rappresenta una specializzazione del primo. A questo punto, consideriamo un generico programma P''' scritto nel linguaggio M ('''PM) e separiamo in suoi dati in ingresso il due sottoinsiemi IS e ID tali che: * IS contiene solo i dati statici ovvero i dati su cui è possibile effettuare una specializzazione. * ID contiene i restanti dati dinamici. PM: IS x ID -> Output Si ha, come abbiamo visto nell'esempio precedente della specializzazione della funzione f5, che: peval(PM, IS) = P' dove P'(ID) = PM(IS, ID); queste equazioni descrivono le proprietà del valutatore parziale. Proiezioni di Futamura Un esempio particolarmente interessante di questo, fu descritto la prima volta nel 1970 da Yoshihiko Futamura, quando venne considerato come programma un interprete per un linguaggio di programmazione, come tale può anch'esso essere parzialmente valutato. Supponiamo di avere un interprete scritto in M del linguaggio L (ILM); l'interprete riceve due dati in ingresso, un programma scritto in L (PL) ed il codice sorgente IS. Specializziamo l'interprete rispetto ad un particolare programma progL: peval(int, prog) = int' tale che ∀s -> int'(s) = int(prog, s) Quindi fissato un programma, int(prog, s) è equivalente a int'(s), ma int'(s) allora è la traduzione di prog da L''' a '''M, ossia il risultato della compilazione di '''prog' sulla macchina astratta M'' (prima proiezione di Futamura). intˁ ''' tra l'altro rappresenta una versione dell'interprete che esegue solo il codice sorgente ed è indipendente da '''prog, è scritto nel linguaggio dell'interprete ed è eseguito più velocemente rispetto alla classica interpretazione. Supponiamo ora che anche peval sia scritto nel linguaggio M''', allora è possibile applicare '''peval a peval stesso. Dato che i parametri di peval sono un programma scritto in M''' e dei dati specializzati, nulla vieta di applicare a '''peval come programma peval stesso e come dati un interprete del linguaggio L''': peval(peval, int) = peval' tale che per ogni '''prog, peval'(prog) = peval(int, prog) dalla prima proiezione di Futamura sappiamo che peval(int, prog) dà come risultato il codice compilato di prog. Dunque peval' è il compilatore da L a M (seconda proiezione di Futamura). "In questo modo si può convertire sistematicamente un interprete nel corrispondente compilatore" In fine applichiamo peval a peval e peval: peval(peval, peval) = peval' tale che per ogni int si ha: peval'(int) = peval(peval, int) per la seconda proiezione di Futamura si ha anche che peval(peval, int) dà come risultato il compilatore da L''' a '''M. Dunque peval' è un programma di M''' che, dato un interprete del linguaggio L scritto in M, produce il compilatore da L a M: peval' è un generatore di compilatori per M, o compiler compiler ('''terza proiezione di Futamura). Fonti * Reprinted in Higher-Order and Symbolic Computation 12 (4): 381–391, 1999, with a foreword. * Voci correlate * Teorema SMN * Metaprogrammazione Collegamenti esterni * [http://www.itu.dk/people/sestoft/pebook/ Neil D. Jones, Carsten K. Gomard, and Peter Sestoft: Partial Evaluation and Automatic Program Generation (1993)] Book, full text available online. * partial-eval.org - a large "Online Bibliography of Partial Evaluation Research". * 1999 ACM SIGPLAN Workshop on Partial Evaluation and Semantics-Based Program Manipulation (PEPM'99) * C++ Templates as Partial Evaluation, 1999 ACM SIGPLAN Workshop on Partial Evaluation and Semantics-Based Program Manipulation (PEPM'99) Categoria:Programmazione Categoria:Linguaggi di programmazione